#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr)
            return {};

        vector<int> ans;
        stack<TreeNode*> st;
        TreeNode* cur = root;

        while (cur || (!st.empty()))
        {
            while (cur)
            {
                st.push(cur);
                ans.push_back(cur->val);
                cur = cur->left;
            }

            TreeNode* top = st.top();
            st.pop();

            cur = top->right;

        }
        return ans;
    }
};